﻿// 0815train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

/*
 其中 prerequisites[i] = [a(i), b(i)] ，表示在选修课程 a(i) 前 必须 先选修 b(i) 。
- 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。
如果不可能完成所有课程，返回 一个空数组

示例2
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
 */

vector<int>solve01(int numCourses, vector<vector<int>>& prerequisites)
{
    //indegree unordered_map<int,vector<int>>touched_map queue

    vector<int>indegree_vec(numCourses);
    unordered_map<int, vector<int>>touched_map;
    int grid_size = prerequisites.size();
    
    for (auto&require_vec: prerequisites)
    {
        int arrive_node = require_vec[0];
        int start_node = require_vec[1];

        touched_map[start_node].push_back(arrive_node);
        indegree_vec[arrive_node]++;
    }

    queue<int>bfs_queue;
    vector<int>result_vec;
    //indegree为0才可以放进去
    for (int node=0; node<indegree_vec.size(); node++)
    {
        if (indegree_vec[node]==0)
        {
            bfs_queue.push(node);
            
        }
    }

    
    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();

        for (int i=0; i<q_size; i++)
        {
            int top_node = bfs_queue.front();
            result_vec.push_back(top_node);
            bfs_queue.pop();

            vector<int>node_vec = touched_map[top_node];

            for (auto&touched_node:node_vec)
            {
                indegree_vec[touched_node]--;

                if (indegree_vec[touched_node]==0)
                {
                    bfs_queue.push(touched_node);
                }

                //for touched_node
            }

            

            //for------
        }

        //while (!bfs_queue.empty())
    }

    bool is_varify = true;
    for (auto&degree:indegree_vec)
    {
        if (degree!=0)
        {
            is_varify = false;
            break;
        }

    }
    if (!is_varify) return {};

    return result_vec;
    //solve01------
}

/*
 输入描述
输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号->表示依赖方向，
例A->B表示A依赖B，多个依赖之间用单个空格分割

输出描述
输出为排序后的启动任务列表，多个任务之间用单个空格分割

示例1
输入
A->B C->B
输出
B A C

说明
任务A和C都依赖于任务B。任务B执行后，A和C立即执行，A和C的执行顺序按照字典序排列

B->A B->C
 */

void solve02(vector<vector<string>>&grid)
{
    //char_set统计有多少个任务
    unordered_set<string>char_set;
    for (auto&require_vec:grid)
    {
        char_set.insert(require_vec[0]);
        char_set.insert(require_vec[1]);
    }
    
    unordered_map<string, int>indegree_map;
    for (auto&node:char_set)
    {
        //所有节点加入indegree
        indegree_map[node] = 0;
    }

    unordered_map<string, vector<string>>touched_map;
    queue<string>bfs_queue;

    //更新touched_map,indegree_map
    for (auto&require_vec:grid)
    {
        string arrive_node = require_vec[0];
        string start_node = require_vec[1];

        touched_map[start_node].push_back(arrive_node);
        indegree_map[arrive_node]++;
    }

    //for (auto&node:indegree_map)
    //{
    //    cout << node.first << ' ' << node.second << endl;
    //}

    //degree为0的节点入队
    for (auto&map_item:indegree_map)
    {
        string node = map_item.first;
        if (map_item.second==0)
        {
            bfs_queue.push(node);
        }
    }

    vector<string>result_vec;
    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();

        vector<string>same_level_vec;
        for (int i=0; i<q_size; i++)
        {
            string top_node = bfs_queue.front();
            bfs_queue.pop();
            same_level_vec.push_back(top_node);

            vector<string>curr_vec = touched_map[top_node];

            for (auto&node:curr_vec)
            {
                indegree_map[node]--;
                if (indegree_map[node]==0)
                {
                    bfs_queue.push(node);
                }

            }

            //for------
        }
        sort(same_level_vec.begin(), same_level_vec.end());
        for (auto&str:same_level_vec)
        {
            result_vec.push_back(str);
        }

        //while (!bfs_queue.empty())
    }
    for (auto&node:result_vec)
    {
        cout << node << ' ';
    }

    //solve02------
}


/*
 给定一个有向图，图中可能包含有环，有向边用两个节点表示。
 第一个整数表示起始节点，第二个整数表示终止节点，如0 1表示存在从0到1的路径。
 每个节点用正整数表示，求这个数据的头节点与尾节点，题目给的用例会是一个头节点，但可能存在多个尾节点。
 同时，图中可能含有环，如果图中含有环，返回-1。

说明：入度为0是头节点，出度为0是尾节点

输入描述
第一行为后续输入的键值对数量N >= 0，第二行为2N个数字。每两个为一个起点，一个终点。

输出描述
输出一行头节点和尾节点。如果有多个尾节点，按从小到大的顺序输出。

备注
如果图有环，输出为-1
所有输入均合法，不会出现不配对的数据

输入
4
1 2 1 3 2 4 3 4
输出
1 4
 */

void solve03(vector<vector<int>>&grid)
{
    //bfs_queue indegree_map touched_map

    //统计全部的节点
    unordered_set<int>oh_set;

    for (auto&oh_vec:grid)
    {
        oh_set.insert(oh_vec[0]);
        oh_set.insert(oh_vec[1]);
    }

    unordered_map<int, int>indegree_map;
    unordered_map<int, vector<int>>touched_map;

    for (auto&num:oh_set)
    {
        indegree_map[num] = 0;
    }
    //更新入度表
    for (auto&touched_vec: grid)
    {
        int start_node = touched_vec[0];
        int arrive_node = touched_vec[1];

        touched_map[start_node].push_back(arrive_node);

        indegree_map[arrive_node]++;
        //for------
    }

    int result_head = -1;
    vector<int>result_tail_vec;

    queue<int>bfs_queue;
    //degree为0是头节点
    for (auto&node_item: indegree_map)
    {
        if (node_item.second==0)
        {
            result_head = node_item.first;
            bfs_queue.push(node_item.first);
        }

        //关系表里没有，说明出度为0，是结尾
        if (touched_map.count(node_item.first) == 0)
        {
            result_tail_vec.push_back(node_item.first);
        }

    }

    while (!bfs_queue.empty())
    {
        //更新degree，判断是否合法
        int top_node = bfs_queue.front();
        bfs_queue.pop();

        vector<int>curr_vec = touched_map[top_node];
        for (auto&node:curr_vec)
        {
            indegree_map[node]--;

            if (indegree_map[node]==0)
            {
                bfs_queue.push(node);
            }
        }
        //while (!bfs_queue.empty())
    }

    bool is_verify = true;
    for (auto&node_item:indegree_map)
    {
        if (node_item.second!=0)
        {
            is_verify = false;
            break;
        }
    }

    if (!is_verify)
    {
        cout << -1;
        return;
    }

    cout << result_head << ' ';

    sort(result_tail_vec.begin(), result_tail_vec.end());
    for (auto&num:result_tail_vec)
    {
        cout << num << ' ';
    }

    //solve03------
}


int main()
{
	{
        //4
		//1 2 1 3 2 4 3 4
        int grid_size;
        cin >> grid_size;
        vector<vector<int>>grid(grid_size);

        for (int i=0; i<grid_size; i++)
        {
            vector<int>require_vec(2);
            cin >> require_vec[0];
            cin >> require_vec[1];
            grid[i] = require_vec;
        }

        //for (auto&require_vec:grid)
        //{
	       // for (auto&num:require_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}

        //vector<vector<int>>grid = {{1,2},{1,3},{2,4},{3,4}};
        solve03(grid);
        return 0;
	}


	{
        //A->B C->B
        //kYAJ->tME TD->I kYAJ->aXbID xlgT->r Y->I xlgT->I kYAJ->TD kYAJ->xlgT adyBD->I
        //string str = "kYAJ->tME";
        //int end_0 = str.find('-');
        //string sub_0 = str.substr(0, end_0);
        //int end_1 = str.find('>');
        //string sub_1 = str.substr(end_1+1);

        //cout << sub_0 << ' ' << sub_1 << endl;

        vector<vector<string>>grid;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
        	int end_0 = token.find('-');
			string node_0 = token.substr(0, end_0);
			int end_1 = token.find('>');
			string node_1 = token.substr(end_1+1);
            vector<string>char_vec = { node_0, node_1 };
            grid.push_back(char_vec);
        }

        //for (auto&char_vec:grid)
        //{
        //    for (auto&oh_char:char_vec)
        //    {
        //        cout << oh_char << ' ';
        //    }
        //    cout << '\n';
        //}

        //vector<vector<char>>grid = { {'A','B'},{'C','B'} };
        solve02(grid);
        return 0;
        //
	}

    //numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
    int numCourses = 4;
    vector<vector<int>>prerequisites = { {1,0},{2,0},{3,1},{3,2} };
    vector<int>result_vec = solve01(numCourses, prerequisites);

    for (auto&num:result_vec)
    {
        cout << num << ' ';
    }

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
